package seqList;

/**
 * 顺序表类，实现线性表接口
 */
public class SeqList<T> implements LList<T> {
    protected Object[] element; // 对象数组，保护成员
    protected int len; // 顺序表长度，记载元素个数

    /**
     * 构造方法， 创建容量为size的空表
     *
     * @param size
     */
    public SeqList(int size) {
        this.element = new Object[size]; // 若size<0，抛出负数组长度异常NegativeArraySizeException
        this.len = 0;
    }

    /**
     * 创建默认容量的空表
     */
    public SeqList() {
        this(64);
    }

    /**
     * 使用随机整数数组创建一个顺序表
     *
     * @param random
     */
    public SeqList(Integer[] random) {
        // TODO Auto-generated constructor stub
    }

    public SeqList(Object[] element) {
        this.element = element;
        this.len = element.length;
    }
    /**
     * 判断顺序表是否空，若空返回true，O(1)
     */
    public boolean isEmpty() {
        return this.len == 0;
    }

    /**
     * 返回顺序表长度，O(1)
     */
    public int length() {
        return this.len;
    }

    /**
     * 按照序号查找 返回第i（≥0）个元素。若i<0或大于表长则返回null，O(1)
     */
    public T get(int i) throws Exception {
        if (i >= 0 && i < this.len) {
//            System.out.println("position=" + i + ",is:" + this.element[i]);
            return (T) this.element[i];
        }
        // return this.element[i]; //编译错，Object对象不能返回T对象
        return null;
    }

    /**
     * 按照内容查找 返回第1个相同数据值的元素
     */
    public T get(T obj) {
        return null;
    }

    // 设置第i（≥0）个元素值为x。若i<0或大于表长则抛出序号越界异常；若x==null，不操作
    public void set(int i, T x) {
        if (x == null)
            return; // 不能设置空对象
        if (i >= 0 && i < this.len)
            this.element[i] = x;
        else
            throw new IndexOutOfBoundsException(i + ""); // 抛出序号越界异常
    }

    // 返回顺序表所有元素的描述字符串，形式为“(,)”，覆盖Object类的toString()方法
    @Override
    public String toString() {
        String str = "顺序表: (";
        if (this.len > 0)
            str += this.element[0].toString();
        for (int i = 1; i < this.len; i++)
            str += ", " + this.element[i].toString();
        return str + "), length=" + this.len; // 空表返回()
    }

    /**
     * 顺序表的插入操作 插入第i（≥0）个元素值为x。
     * * 若x==null，不插入。
     * * 若i<0，插入x作为第0个元素；
     * * 若i大于表长，插入x作为最后一个元素
     */
    public void insert(int i, T x) {
        // 防御性代码
        // 对于插入位置和值进行合法性判断
        if (x == null)
            return; // 不能插入空对象
        if (i < 0)
            i = 0; // 下标容错
        if (i > this.len)
            i = this.len;
        if (this.len == element.length) {   // 若数组满，则扩充顺序表容量
            Object[] temp = this.element; // temp也引用elements数组
            this.element = new Object[temp.length * 2]; // 重新申请一个容量更大的数组
            for (int j = 0; j < temp.length; j++) // 复制数组元素，O(n)
                this.element[j] = temp[j];
        }
//        System.out.println("insert a new node:" + x + ",in position=" + i);
        // 元素后移，平均移动len/2
        for (int j = this.len - 1; j >= i; j--)
            this.element[j + 1] = this.element[j];
        // 存储新数据元素
        this.element[i] = x;
        // 增加表仓储
        this.len++;
    }

    /**
     * 在顺序表最后插入x元素
     *
     * @param x
     */
    public void append(T x) {
        insert(this.len, x);
    }

    /**
     * 顺序表的删除操作 删除第i（≥0）个元素，返回被删除对象。若i<0或i大于表长，不删除，返回null。
     */
    public T remove(int i) throws Exception {
        if (this.len == 0 || i < 0 || i >= this.len) {
            // throw new IndexOutOfBoundsException(i + ""); // 抛出序号越界异常
            System.out.println("delete position=" + i + ",is out index!!!");
            return null;
        }
        // 把被删除元素的数据值给其他变量
        T old = (T) this.element[i];
        System.out.println("node:" + old + ",is deleted from seqlist.");
        // 把位置i后面的数据元素依次向前移动，平均移动len/2
        for (int j = i; j < this.len - 1; j++) {
            this.element[j] = this.element[j + 1];
        }
        this.element[this.len - 1] = null;
        // 顺序表的长度-1
        this.len--;
        return old;
    }

    /**
     * 删除线性表所有元素
     */
    public void removeAll() {
        this.len = 0;
    }

    /**
     * 查找首次与 key 相等的数据元素
     *
     * @param key 待查找元素
     * @return 返回数据元素的序号, 找不到则返回-1
     */
    public int search(T key) {
        for (int i = 0; i < this.len; i++) {
            if (key.equals(this.element[i])) {
                return i;
            }
        }
        return -1;
    }

    public boolean contain(T x) {
        return false;
    }

    public void showListInfo() {
        System.out.println("seqlist:" + this.toString() + ", length=" + this.len);
    }

    public T[] getElements() {
        return (T[]) this.element;
    }
}
